package sit.engreal.leetcode.problems200;

import java.util.ArrayDeque;
import java.util.ArrayList;

/**
 * <a href="https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/">
 * 116. 填充每个节点的下一个右侧节点指针
 * </a>
 */
public class LeetCode116 {
    public static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        final ArrayList<Node> nodes = new ArrayList<>();
        final ArrayDeque<Node> deque = new ArrayDeque<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            while (!deque.isEmpty()) {
                nodes.add(deque.removeFirst());
            }
            for (int i = 0; i < nodes.size() - 1; i++) {
                nodes.get(i).next = nodes.get(i + 1);
            }

            for (Node node : nodes) {
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
            }
            nodes.clear();
        }
        return root;
    }

    public static void main(String[] args) {
        final Node root = new Node(1,
                new Node(2,
                        new Node(4),
                        new Node(5),
                        null),
                new Node(3,
                        new Node(6),
                        new Node(7),
                        null),
                null);

        final LeetCode116 demo = new LeetCode116();
        demo.connect(root);

    }
}
